1. Technical Field of the Invention
The invention relates generally to decoding of signals within communication systems; and, more particularly, it relates to trellis decoding of signals that involve performing traceback of at least one surviving path within a block.
2. Description of Related Art
Data communication systems have been under continual development for many years. One such type of communication system that has been of significant interest lately is a communication system that employs iterative error correction codes. Communications systems with iterative codes are often able to achieve lower bit error rates (BER) than alternative codes for a given signal to noise ratio (SNR).
A continual and primary directive in this area of development has been to try continually to lower the SNR required to achieve a given BER within a communication system. The ideal goal has been to try to reach Shannon's limit in a communication channel. Shannon's limit may be viewed as being the data rate to be used in a communication channel, having a particular SNR, that achieves error free transmission through the communication channel. In other words, the Shannon limit is the theoretical bound for channel capacity for a given modulation and code rate.
As is known, many varieties of memory storage devices (e.g. hard disk drives (HDDs)), such as magnetic disk drives are used to provide data storage for a host device, either directly, or through a network such as a storage area network (SAN) or network attached storage (NAS). Such a memory storage system (e.g., a HDD) can itself be viewed as a communication system in which information is encoded and provided via a communication channel to a storage media; the reverse direction of communication is also performed in a HDD in which data is read from the media and passed through the communication channel (e.g., sometimes referred to as a read channel in the HDD context) at which point it is decoded to makes estimates of the information that is read.
Typical host devices include stand alone computer systems such as a desktop or laptop computer, enterprise storage devices such as servers, storage arrays such as a redundant array of independent disks (RAID) arrays, storage routers, storage switches and storage directors, and other consumer devices such as video game systems and digital video recorders. These devices provide high storage capacity in a cost effective manner.
Of the many types of communication systems that have received interest in recent years, many of them undesirably introduce some degree of ISI (Inter-Symbol Interference) to signal transmitted therein. The read (and write) channel of a hard disk drive (HDD) (which can itself be viewed as being a communication channel within a communication system) is one such communication channel that oftentimes introduces ISI. One solution to address and combat the undesirable effects of ISI is to employ some form of error correction code (ECC) to encode information being passed through such a communication channel that may undesirably suffer from ISI.
For example, such encoding (e.g., in accordance with an ECC) may be performed in many steps and such encoding steps may vary from device to device. The encoding steps include, but are not limited to, addition of a preamble (bits pre-pended to the data unit (e.g., a data sector) to facilitate determination of the phase of the analog data signal from the disc), a sync mark (bits placed between the preamble and encoded user data to identify the start of the encoded user data), modulation coding (any scheme that makes the user data easier to read by the reading mechanism of the device; this type of encoding “transforms” the bit sequence, often making it substantially different in appearance from the original user data), and error correction coding (bits appended to the encoded user data that allows correction of some limited number of errors that may have occurred during retrieval). The main point is that several common (but variable) procedures are invoked to improve the robustness and readability of the data stored in the device.
Within such hard disk drives (HDDs), disk drive controllers control the various processes associated with the read/write of data to the physical media. As the amount of data stored to the physical media increases, the ability accurately to read data from the physical media is adversely effected. Again, one factor affecting the ability to accurately read this data is ISI (Inter-Symbol Interference). Although discussed here as a problem associated with HDDs, this problem may be present within any communication channel (as also stated above).
To allow higher storage within physical media such as that of a hard disk drive (HDD), one solution in telecommunications and data storage has been to intentionally write symbols close together and utilize the Viterbi algorithm (or any other sequence detector) and knowledge of how the symbols interact to recover the bit sequence from a noisy analog signal. When applying this solution, the data interferes in a controlled manner and additionally becomes distorted by noise and/or other interfering signals. This noise and interfering signals must be overcome in order to properly read back the pattern of “1's” and “0's” correctly. The Viterbi algorithm is an efficient dynamic programming algorithm that finds the most likely sequence of bits received by comparing a received sequence of points sampled from the analog read back waveform to every possible sequence of bits transmitted. This best sequence is referred to as the “best path through the trellis.” The trellis tracks all possible paths and consists of states, which help track the bit decisions associated with the path through them. Other techniques design symbols that are more robust against ISI. Decreasing the symbol rate (e.g., the “baud rate”), and keeping the data bit rate constant (by coding more bits per symbol), reduces ISI.
A sizable market has developed for these data storage devices and the price per unit of storage has steadily dropped. A similar market has developed for high capacity communication channels. As increased capacity within communication channels and data storage devices are provided, the need to retrieve data from these communication channels and data storage devices with greater accuracy continues to grow.